import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Test {
    //和为s的两个数字
    public int[] twoSum(int[] price, int target) {
        int[] ret = new int[2];
        int left = 0;
        int right = price.length - 1;
        while(left < right){
            if(price[left] + price[right] > target){
                right--;
            }else if(price[left] + price[right] < target){
                left++;
            }else {
                ret[0] = price[left];
                ret[1] = price[right];
                return ret;
            }
        }
        return ret;
    }

    //...
        public List<List<Integer>> threeSum(int[] nums) {
            //排序
            Arrays.sort(nums);
            List<List<Integer>> ret = new LinkedList<>();
            //双指针算法
            for(int i = 0;i < nums.length;){
                if (nums[i] > 0) {//小优化
                    break;
                }
                int left = i + 1;
                int right = nums.length - 1;
                int target = -nums[i];
                while(left < right){
                    int sum = nums[left] + nums[right];
                    if(sum > target){
                        right--;
                    }else if(sum < target){
                        left++;
                    }else {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        ret.add(list);
                        //这些需要放在else里面 然后调整left 和 right 的值
                        left++;
                        right--;
                        //去重：left right
                        while(left < right && nums[left] == nums[left-1]){
                            left++;
                        }
                        while(left < right && nums[right] == nums[right + 1]){
                            right--;
                        }
                    }
                }
                i++;
                //去重 i
                while(i < nums.length && nums[i] == nums[i - 1]){
                    i++;
                }
            }
            return ret;
        }
        //四数之和

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        //排序
        Arrays.sort(nums);
        int n = nums.length;
        for(int i = 0;i < n;){
            //利用三数之和的思想完成
            for (int j = i + 1; j < n;) {
                long aim = (long) target - nums[i] - nums[j];//这里可能会发生数据溢出的现象
                int left = j + 1;
                int right = n - 1;
                while(left < right){
                    int sum = nums[left] + nums[right];
                    if(sum > aim){
                        right--;
                    }else if(sum < aim){
                        left++;
                    }else {
                        ret.add(new ArrayList<>(Arrays.asList(nums[i],nums[j],nums[left],nums[right])));
                        left++;
                        right--;
                        while(left < right && nums[left] == nums[left - 1]){
                            left++;
                        }
                        while(left < right && nums[right] == nums[right + 1]){
                            right--;
                        }
                    }
                }
                j++;
                while(j < n && nums[j] == nums[j - 1]){
                    j++;
                }
            }
            i++;
            while(i < n && nums[i] == nums[i-1]){
                i++;
            }
        }
        return ret;
    }

}
